/*
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see http://www.gnu.org/licenses/. 
 *
 *  Authors:
 *  	Albert Marieges Garcia
 *  	Álex Pardo Fernández
 *  	Enric Mayas Márquez
 *  	Juan Carlos Calvo Tejedor
 *  	Marc Gironés Dezsényi
 *  
 *  Contact:
 *  	bcn.tours.android@gmail.com
 *  Webpage:
 *  	bcntours.co.cc
 *
 */
package com.BCNTours.AR.Utils;

import java.util.ArrayList;

import com.BCNTours.AR.Vista.POIButton;
 
/**
 * Support class that sorts a given list of POI, depending on how far they are from the user,
 * being the closest POI the first member of the sorted list. This will allow POIButtons to be drawn
 * with a priority depending on their distance, and will make the closest POI to be drown above the farthest ones.
 */
public class Quicksort {
 
    public static final int NUMBERS_TO_SORT = 25;
 
    /**
     * Constructor of the class.
     */
    public Quicksort() {
    }
    
    /**
     * Given a list of POIs, does an inverse sort by distance.
     * @param pois Initial list of POIs
     * @return	   Sorted list of POIs
     */
    public static ArrayList<POIButton> quicksort(ArrayList<POIButton> pois) {
        if (pois.size() <= 1)
            return pois;
        int pivot = pois.size() / 2;
        ArrayList<POIButton> lesser = new ArrayList<POIButton>();
        ArrayList<POIButton> greater = new ArrayList<POIButton>();
        int sameAsPivot = 0;
        for (POIButton p : pois) {
            if (p.getDistance() > pois.get(pivot).getDistance())
                greater.add(p);
            else if (p.getDistance() < pois.get(pivot).getDistance())
                lesser.add(p);
            else
                sameAsPivot++;
        }
        lesser = quicksort(lesser);
        for (int i = 0; i < sameAsPivot; i++)
            lesser.add(pois.get(pivot));
        greater = quicksort(greater);
        ArrayList<POIButton> sorted = new ArrayList<POIButton>();
        for (POIButton p : lesser)
            sorted.add(p);
        for (POIButton p: greater)
            sorted.add(p);
        return sorted;
    }
}